#include "SoftGPU.h"
#include "assimp/Importer.hpp"
#include "assimp/scene.h"
#include "assimp/postprocess.h"
#include "assimp/mesh.h"
#include <algorithm>
#include <random>

namespace mz{

inline DirectX::XMVECTOR operator * (const DirectX::XMVECTOR& vec, const float f)
{
	return DirectX::XMVectorMultiply(vec, DirectX::XMVectorSet(f,f,f,1.f));
}

inline DirectX::XMVECTOR operator + (const DirectX::XMVECTOR& vec1, const DirectX::XMVECTOR& vec2)
{
	return DirectX::XMVectorAdd(vec1, vec2);
}

inline DirectX::XMVECTOR operator - (const DirectX::XMVECTOR& vec1, const DirectX::XMVECTOR& vec2)
{
	return DirectX::XMVectorSubtract(vec1, vec2);
}

DirectX::XMVECTOR Original = DirectX::XMVectorSet(0.f, 0.f, 0.f, 1.f);

inline int Map(float f, int total, bool head){
	if(head) return std::floor((f+1.f)*total/2.f + 0.5f);
	else return std::floor((f+1.f)*total/2.f - 0.5f);
}

inline float Map(int i, int total){
	return (2.f/total)*(i+0.5f) - 1.f;
}

template <typename Type>
inline Type Max(Type x, Type y, Type z){
	return std::max(x, std::max(y, z));
}

template <typename Type>
inline Type Min(Type x, Type y, Type z){
	return std::min(x, std::max(y, z));
}

}



bool mz::SoftGPU::Init(const std::string& modelPath, const DirectX::XMMATRIX& matrix, int width, int height)
{
	//load model from file to mem
	Assimp::Importer importer;
	const aiScene* scene = importer.ReadFile(modelPath.c_str(), aiProcess_Triangulate|aiProcess_ConvertToLeftHanded);

	if(!scene || scene->HasMeshes() == false) return false;
	//only process mesh 0
	if(scene->mNumMeshes > 1)
		printf("Warnning: more than 1 mesh in the model\n");
	auto mesh = scene->mMeshes[0];
	if(mesh->HasFaces() == false) return false;
	
	for(int f = 0; f < mesh->mNumFaces; f++)
	{
		const auto& face = mesh->mFaces[f];
		if(face.mNumIndices != 3) return false;
		auto& vert0 = mesh->mVertices[face.mIndices[0]];
		auto& vert1 = mesh->mVertices[face.mIndices[1]];
		auto& vert2 = mesh->mVertices[face.mIndices[2]];
		m_primitives.push_back(Primitive(vert0.x, vert0.y, vert0.z, vert1.x, vert1.y, vert1.z, vert2.x, vert2.y, vert2.z));
	}

	//init param
	m_matrix = matrix;
	m_width = width;
	m_height = height;

	//alloc zbuffer and cbuffer
	m_zBuffer = new float[width];
	for(int i = 0; i < width; i++)
		m_zBuffer[i] = 1.f;

	m_cBuffer = new unsigned char[width*height*3];
	std::memset(m_cBuffer, 0, width*height*3*sizeof(unsigned char));

	return true;
}

void mz::SoftGPU::Free()
{
	m_primitives.clear();
	delete [] m_zBuffer;
	m_zBuffer = nullptr;
	delete [] m_cBuffer;
	m_cBuffer = nullptr;
}

void mz::SoftGPU::TransformAndClip()
{
	for(auto& prim : m_primitives){
		for(auto& vert : prim.vertices){
			vert = DirectX::XMVector4Transform(vert, m_matrix);
			float w = vert.m128_f32[3];
			vert = DirectX::XMVectorDivide(vert, DirectX::XMVectorSet(w,w,w,w));
			vert.m128_f32[3] = 1.f;
		}

		prim.normal = DirectX::XMVector4Transform(prim.normal, m_matrix);

		prim.yMax = std::max(
			prim.vertices[0].m128_f32[1], 
			std::max(prim.vertices[1].m128_f32[1], prim.vertices[2].m128_f32[1])
			);
		prim.stride = prim.yMax - std::min(
			prim.vertices[0].m128_f32[1], 
			std::min(prim.vertices[1].m128_f32[1], prim.vertices[2].m128_f32[1])
			);
	}

	m_primitives.erase(std::remove_if(m_primitives.begin(), m_primitives.end(), [](const Primitive& prim){
		//back face clip
		//mz trace
//		if(prim.normal.m128_f32[2] > 0.f) return true;

		//out of range clip
		for(int axis = 0; axis < 3; axis++){
			float max = Max(prim.vertices[0].m128_f32[axis], prim.vertices[1].m128_f32[axis], prim.vertices[2].m128_f32[axis]);
			if(max < -1.f) return true;
			float min = Min(prim.vertices[0].m128_f32[axis], prim.vertices[1].m128_f32[axis], prim.vertices[2].m128_f32[axis]);
			if(min > 1.f) return true;
		}
		return false;
	}), m_primitives.end());

}

unsigned char* mz::SoftGPU::Scan()
{
	TransformAndClip();

	//prepare list
	std::sort(m_primitives.begin(), m_primitives.end());
	
	float curLine = 1.f - 1.f/m_height;
	float yStride = -2.f/m_height;
	float xStride = 2.f/m_width;

	//prepare active line pair list
	std::vector<EdgePair> activeEdgePairs;
	EdgePair tmpPair;

	auto primItr = m_primitives.begin();

	for( ; primItr != m_primitives.end(); primItr++)
		if(primItr->yMax > curLine && primItr->yMax - primItr->stride < curLine){
			if(GetEdgePair(*primItr, curLine, tmpPair))
				activeEdgePairs.push_back(tmpPair);
		}else
			break;

	//start scan
	//all scanlines
	for(int y = m_height-1; y >= 0; y--)
	{
		//all active pairs
		for(auto& pair : activeEdgePairs)
		{
			//all x values
			int start = Map(pair[0].cx, m_width, true);
			int end = Map(pair[1].cx, m_width, false);

			//ensure clip
			int x = std::max(start, 0);
			float vx = Map(x, m_width);
			float kz = (pair[1].cz-pair[0].cz)/(pair[1].cx-pair[0].cx);
			float vz = pair[0].cz + kz*(vx - pair[0].cx);

			float zStrideByX = xStride * kz;

			for(; x <= end && x < m_width; x++)
			{
				//compare z depth be careful with starnge values [-1,1]
				if(m_zBuffer[x] > vz){
					m_zBuffer[x] = vz;
					//shading
					int cIndex = (m_width * y + x)*3;

					auto ret = DirectX::XMVector3Dot(pair.GetParentPrim().normal, DirectX::XMVectorSet(0.f, 0.f, -1.f, 0.f));
					unsigned char cVal = unsigned char(ret.m128_f32[0]*256.f);

					m_cBuffer[cIndex]   = pair.GetParentPrim().r;
					m_cBuffer[cIndex+1] = pair.GetParentPrim().g;
					m_cBuffer[cIndex+2] = pair.GetParentPrim().b;
				}
				vx += xStride;
				vz += zStrideByX;
			}
		}


		//deal with avtive EdgePair list
		curLine += yStride;

		int end = activeEdgePairs.size();
		
		EdgePair newPair;

		for(int i = 0; i < end; i++){
			EdgePair& pair = activeEdgePairs[i];
			//process pairs && add new pair
			if(pair.nextScanLine(curLine, -yStride))
				if(GetEdgePair(pair.GetParentPrim(), curLine, newPair))
					activeEdgePairs.push_back(newPair);

		}
		//remove passed EdgePairs
		activeEdgePairs.erase(
			std::remove_if(activeEdgePairs.begin(), activeEdgePairs.end(), [curLine](const EdgePair& pair){
				return pair[0].ey > curLine || pair[1].ey > curLine;
			}),
			activeEdgePairs.end());

		//add new suitable pairs
		for(; primItr != m_primitives.end(); primItr++){
			if(primItr->yMax > curLine){
				if(GetEdgePair(*primItr, curLine, newPair))
					activeEdgePairs.push_back(newPair);
			}else{
				break;
			}
		}

		//clear zbuffer
		for(int i = 0; i < m_width; i++)
			m_zBuffer[i] = 1.f;
		//start new loop
	}

	return m_cBuffer;
}

mz::SoftGPU::~SoftGPU()
{
	if(!m_zBuffer) delete [] m_zBuffer;
	if(!m_cBuffer) delete [] m_cBuffer;
}

bool mz::Primitive::operator<(const Primitive& p)
{
	return yMax > p.yMax;
}

mz::Primitive::Primitive(float x0, float y0, float z0, float x1, float y1, float z1, float x2, float y2, float z2)
{
	vertices[0] = DirectX::XMVectorSet(x0, y0, z0, 1.f);
	vertices[1] = DirectX::XMVectorSet(x1, y1, z1, 1.f);
	vertices[2] = DirectX::XMVectorSet(x2, y2, z2, 1.f);

	auto u = vertices[2] - vertices[0];
	auto v = vertices[1] - vertices[0];
	normal = DirectX::XMVector3Cross(v, u);
	normal = DirectX::XMVector3Normalize(normal);

	//random 
	r = unsigned char(((float)rand()/RAND_MAX) * 256.f);
	g = unsigned char(((float)rand()/RAND_MAX) * 256.f);
	b = unsigned char(((float)rand()/RAND_MAX) * 256.f);

}

bool mz::GetEdgePair(const Primitive& prim, const float curLine, EdgePair& pair)
{
	for(int i = 0, j = 1, ip = 0; i < 3; i++, j = (j+1)%3)
	{
		//p.y is bigger than q.y
		DirectX::XMVECTOR p, q, intersection;
		if(prim.vertices[i].m128_f32[1] > prim.vertices[j].m128_f32[1]){
			p = prim.vertices[i];
			q = prim.vertices[j];
		}else{
			p = prim.vertices[j];
			q = prim.vertices[i];
		}
		//the edge has no cross with scanline
		if(curLine > p.m128_f32[1] || curLine < q.m128_f32[1])
			continue;
		//p to scanline
		float a = p.m128_f32[1] - curLine;
		float b = curLine - q.m128_f32[1];
		float c = p.m128_f32[1] - q.m128_f32[1];
		a = a/c;
		b = b/c;

		//intersection = (p-Original)*a + (q-Original)*b + Original;
		intersection = p*b + q*a;
		pair[ip].cz = intersection.m128_f32[2];
		pair[ip].cx = intersection.m128_f32[0];
		pair[ip].ey = q.m128_f32[1];
		pair[ip].dx = (q.m128_f32[0] - p.m128_f32[0])/c;
		pair[ip].dz = (q.m128_f32[2] - p.m128_f32[2])/c;
		pair.SetParentPrim(&prim);

		ip++;
		if(ip > 2) return false;
	}

	if(pair[0].cx > pair[1].cx)
		std::swap(pair[0], pair[1]);

	return true;
}
